//
// Created by 28735 on 2024/11/25.
//

#ifndef SEARCH_H
#define SEARCH_H

/*  散列表
 *  1.散列方式：
 *   直接定址法 - h(key) = a * key +b
 *   除留取余法 - h(key) = key mod p
 *   数学分析法
 *  2.冲突处理：
 *   线性探测 - h(key) = key mod p + 1
 *   平方探测 - h(key) = (h(key) +/- i^2) / size i = -1, 1, -2, 2 ......
 *   再哈希法
 *   再散列法（扩容）
 *   冲突链表 - 冲突的数值都放在同一条链表上
 *  3.装填因子 = 散列数量 / 散列表长度
 */

/*  B树：
 *   ①除根结点之外，其他非叶子结点数量不得少于[m/2]向上取整的个数
 *   ②所有结点都存储数据，适合点查询和范围查询，一般用于内存中的数据结构
 *   ③所有叶子节点都在同一层
 *   ④根结点至少有两个子节点
 */

/*  B+树
 *   ①除根结点之外，其他非叶子结点数量不得少于[m/2]向上取整的个数
 *   ②所有结点都存储数据，连接成双向链表，范围查询，一般用于磁盘中的数据结构
 *   ③所有叶子节点都在同一层
 *   ④根结点至少有两个子节点
 */

/*  红黑树
 *   ①结点相邻的子结点和父结点不能同时为红
 *   ②根节点为黑色
 *   ③从根节点开始到叶子节点的路径上黑色结点的数量相同
 *   ④叶子节点都是黑色
 */
#endif //SEARCH_H
